package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by tiang on 2018/9/6.
 */
public class PalindromePartitioning {
    /**
     * Given a string s, partition s such that every substring of the partition is a palindrome.
     Return all possible palindrome partitioning of s.
     Example:
     Input: "aab"
     Output:
     [
     ["aa","b"],
     ["a","a","b"]
     ]
     将字符串s分割成回文序列
     * @param s 字符串
     * @return 回文序列列表
     */
    public List<List<String>> partition(String s) {
        return partition(s, 0);
    }

    /**
     * 从index位置开始，将字符串s分割成多个回文字符串
     * @param s 源字符串
     * @param index 开始位置
     * @return 回文字符串序列
     */
    private List<List<String>> partition(String s, int index){
        if(index == s.length())
            return null;
        List<List<String>> lists = new ArrayList<>();
        // 依次截取子串
        for(int i=index+1;i<=s.length();i++){
            // 判断截取的字符串是否是回文，如果是，就递归，不是的话就接着循环
            String str = s.substring(index, i);
            if(isPalindrome(str)){
                List<List<String>> subResult = partition(s, i);
                if(subResult == null){
                    List<String> arr = new ArrayList<>();
                    arr.add(str);
                    lists.add(arr);
                }else{
                    for(List<String> l : subResult){
                        l.add(0, str);
                        lists.add(l);
                    }
                }
            }
        }
        return lists;
    }

    /**
     * 判断一个字符串是否是回文字符串
     * @param str 源字符串
     * @return 是否回文
     */
    private boolean isPalindrome(String str){
        for(int i=0;i<str.length()/2;i++){
            if(str.charAt(i) != str.charAt(str.length()-i-1))
                return false;
        }
        return true;
    }

    /**
     * Given a string s, partition s such that every substring of the partition is a palindrome.

     Return the minimum cuts needed for a palindrome partitioning of s.

     Example:

     Input: "aab"
     Output: 1
     Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
        最少经过几次切割，能将字符串切割成全部都是回文字符串序列
     * @param s 源字符串
     * @return 最小切割次数
     */
    public int minCut(String s) {
        return minCut(s, 0, new int[s.length()]);
    }

    private int minCut(String s, int index, int[] temp){
        if(index == s.length())
            return -1;
        if(temp[index]!= 0)
            return temp[index];
        int count = Integer.MAX_VALUE;
        // 如果该字符串即为非回文字符串，那么就返回0
        if(isPalindrome(s.substring(index)))
            return 0;
        for(int i=index+1;i<=s.length();i++){
            String str = s.substring(index, i);
            if(isPalindrome(str)){
                count = Integer.min(minCut(s, i, temp)+1, count);
            }
        }
        temp[index] = count;
        return count;
    }
}
